package com.leetcode.周赛.第233场;

import java.util.Arrays;

/**
 * @author: xiaomi
 * @date: 2021/3/21
 * @description: 5711. 有界数组中指定下标处的最大值
 * https://leetcode-cn.com/contest/weekly-contest-233/problems/maximum-value-at-a-given-index-in-a-bounded-array/
 */
public class B_5711_有界数组中指定下标处的最大值 {

    static B_5711_有界数组中指定下标处的最大值 action = new B_5711_有界数组中指定下标处的最大值();

    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
//        test4();
//        test5();
        test6();
//        int sqrt = (int) Math.sqrt(1000);
//        System.out.println("sqrt = " + sqrt);
//        System.out.println("pow = " + Math.pow(31, 2));
    }


    public static void test1() {
        //3
        int n = 6;
        int index = 1, maxSum = 10;
        int res = action.maxValue(n, index, maxSum);
        System.out.println("res = " + res);
    }

    public static void test2() {
        //7
        int n = 3;
        int index = 2, maxSum = 18;
        int res = action.maxValue(n, index, maxSum);
        System.out.println("res = " + res);
    }

    public static void test3() {
        //4
        int n = 8, index = 7, maxSum = 14;
        int res = action.maxValue(n, index, maxSum);
        System.out.println("res = " + res);
    }

    public static void test4() {
        //1
        int n = 4, index = 0, maxSum = 4;
        int res = action.maxValue(n, index, maxSum);
        System.out.println("res = " + res);
    }

    public static void test5() {
        //7
        int n = 3, index = 2, maxSum = 18;
        int res = action.maxValue(n, index, maxSum);
        System.out.println("res = " + res);
    }

    public static void test6() {
        //4
        int n = 8, index = 7, maxSum = 14;
        int res = action.maxValue(n, index, maxSum);
        System.out.println("res = " + res);
    }

    /**
     * 这种算法太麻烦了
     *
     * @param n
     * @param index
     * @param maxSum
     * @return
     */
    public int maxValueFail(int n, int index, int maxSum) {
        //1.average
        int average = maxSum / n;
        ;
        int[] arr = new int[n];
        Arrays.fill(arr, average);
        int diff = maxSum % n;
        if (diff == 0) {
            return average;
        }
        arr[index]++;
        diff--;
        int leftIndex = index - 1;
        int rightIndex = index + 1;
        while (diff > 0) {
            boolean added = false;
            if (leftIndex >= 0) {
                arr[leftIndex]++;
                added = true;
            }
            if (!added) {

            }
        }
        return 1;
    }


    /**
     * 错了，跟 average 没有关系，直接算三角堆即可
     *
     * @param n
     * @param index
     * @param maxSum
     * @return
     */
    public int maxValueFail2(int n, int index, int maxSum) {
        //1.average
        int average = maxSum / n;
        int diff = maxSum % n;
        if (diff == 0) {
            return average;
        }
        // nums[index] >= sqrt+average
        int sqrt = (int) Math.sqrt(diff);
        int singleWidth = sqrt - 1;
        //三角堆的左边界
        int leftIndex = index - singleWidth;
        //三角堆的右边界
        int rightIndex = index + singleWidth;
        if (leftIndex >= 0 && rightIndex < n) {
            return sqrt + average;
        }
        //考虑多余数字的摆放
        int leftNum = 0;
        if (leftIndex < 0) {
            //left 越界

        }

        return 1;
    }

    /**
     * 这个题目有问题：三个正整数 n、index 和 maxSum，但是 index 可以为 0 ；
     * 然后又规定 nums[i] 是 正整数，从测试用例来看，是不允许为 0的。
     * 最后还是解出来了，说明思路是对的，但是速度还是太慢了吧！
     * @param n
     * @param index
     * @param maxSum
     * @return
     */
    public int maxValue(int n, int index, int maxSum) {
        //保证每个数基础值为1
        maxSum = maxSum - n;
        int height = (int) Math.sqrt(maxSum);
        int singleWidth = height - 1;
        int endIndex = n - 1;
        //三角堆的左边界
        int leftIndex = index - singleWidth;
        //三角堆的右边界
        int rightIndex = index + singleWidth;
        //如果三角堆在n 内
        if (leftIndex >= 0 && rightIndex < n) {
            return height + 1;
        }
        //如果三角堆在 n 外
        int leftNum = maxSum - (int) Math.pow(height, 2);
        if (leftIndex < 0) {
            //left 越界
            leftNum += ((0 - leftIndex) * (height - index) >> 1);
        }
        if (rightIndex >= n) {
            leftNum += ((rightIndex - endIndex) * (height - endIndex + index) >> 1);
        }


        int leftTrueIndex = leftIndex <= 0 ? 0 : leftIndex - 1;
        int rightTrueIndex = rightIndex > endIndex ? endIndex : rightIndex + 1;
        int width = rightTrueIndex - leftTrueIndex + 1;

        int lastWidth = 0;
        while (leftNum >= width) {
            leftNum -= width;
            lastWidth = width;
            if (leftTrueIndex != 0) {
                leftTrueIndex--;
                width++;
            }
            if (rightTrueIndex != endIndex) {
                rightTrueIndex++;
                width++;
            }


            height++;
            if (lastWidth==width){
                break;
            }
        }
        height+=leftNum/width;
        return height + 1;
    }
}
